package cn.zzf.algs.note.base.sort;

import cn.zzf.algs.note.base.util.SortUtil;

/**
 * @author GaoFeng2017
 * @date 2020/6/16 19:57
 */
public class InsertionSort implements Sort {

    /** 插入排序 */
    @Override
    public void sort(Comparable[] elements) {
        // 插入排序，从未排序的元素中，选择一个丢入到已排序的元素部分，进行比较交换，当最后一个未排序元素交换完成后整个数组就是有序的。
        // 与冒泡排序的区别：冒泡排序也是两两交换比较，但是比较的对象不同，冒泡排序是比较未排序的部分，将当前未排序元素的最大和最小找出来，
        // 而插入排序则是从未排序的部分选一个丢到已排序的部分，重新排序，
        for (int i = 1; i < elements.length; i++) {
            for (int j = i; j > 0 && SortUtil.less(elements[j], elements[j - 1]); j--) {
                SortUtil.exchange(elements, j, j - 1);
            }
        }
    }

}
